package com.sufen.seckill.study.LeetCode;

/**
 * @Author sufen
 * @Date 2021/11/6 13:22
 * @Version 1.0
 * 功能描述：
 */
public class Offer_13_机器人的运动范围 {
    int count;
    public int movingCount(int m, int n, int k) {
        boolean[][] visited=new boolean[m][n];
        count=0;
        bfs(0,0,k,visited,m,n);
        return count;
    }

    public void bfs(int i,int j,int k,boolean[][] visited,int m,int n){
        if(i<0||i>=m||j<0||j>=n){
            return;
        }
        if(valid(i,j,k)&&!visited[i][j]){
            visited[i][j]=true;
            count++;
            // System.out.println("+1");
            bfs(i-1,j,k,visited,m,n);
            bfs(i+1,j,k,visited,m,n);
            bfs(i,j-1,k,visited,m,n);
            bfs(i,j+1,k,visited,m,n);
        }
    }

    public boolean valid(int i,int j,int k){
        int cI=i/10;
        int yI=i%10;
        int numI=0;
        while(cI!=0){
            numI+=yI;
            yI=cI%10;
            cI/=10;
        }
        numI+=yI;
        //j
        int cJ=j/10;
        int yJ=j%10;
        int numJ=0;
        while(cJ!=0){
            numJ+=yJ;
            yJ=cJ%10;
            cJ/=10;
        }
        numJ+=yJ;

        if(numI+numJ<=k){
            return true;
        }else{
            return false;
        }
    }
}
